graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a perfect matching in a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

is a matching that covers every

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet * Vertex (computer graphics), a data structure that describes the positio ...

of the graph. More formally, given a graph , a perfect matching in is a

subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...

of edge set , such that every vertex in the vertex set is adjacent to exactly one edge in . A perfect matching is also called a 1-factor; see

Graph factorization In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''- regular subgraph, and a ''k''-factorization partitions the edges of the gra ...

for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs: : In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size

edge cover In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size ...

. If there is a perfect matching, then both the matching number and the edge cover number equal . A perfect matching can only occur when the graph has an even number of vertices. A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an

odd number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because \begin -2 \cdot 2 &= -4 \\ 0 \cdot 2 &= 0 \\ 41 ...

of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.

Characterizations

Hall's marriage theorem In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations: * The combinatorial formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a di ...

provides a characterization of bipartite graphs which have a perfect matching. The

Tutte theorem In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs ...

provides a characterization for arbitrary graphs. A perfect matching is a spanning 1-regular subgraph, a.k.a. a 1-factor. In general, a spanning ''k''-regular subgraph is a ''k''-factor. A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Let

G

be a

on even

n

vertices and

\lambda_1 > \lambda_2 > \ldots > \lambda_>0

\frac

distinct nonzero purely imaginary numbers. Then

G

has a perfect matching if and only if there is a real

skew-symmetric matrix In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition In terms of the entries of the matrix, if a_ ...

A

with graph

G

and

eigenvalues In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_

. Note that the (simple) graph of a real symmetric or skew-symmetric matrix

A

of order

n

has

n

vertices and edges given by the nonzero off-diagonal entries of

A

Computation

Deciding whether a graph admits a perfect matching can be done in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

, using any algorithm for finding a

maximum cardinality matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is ad ...

. However, counting the number of perfect matchings, even in bipartite graphs, is #P-complete. This is because computing the

permanent Permanent may refer to: Art and entertainment * ''Permanent'' (film), a 2017 American film * ''Permanent'' (Joy Division album) * "Permanent" (song), by David Cook Other uses * Permanent (mathematics), a concept in linear algebra * Permanent (cy ...

of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its

biadjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

. A remarkable theorem of Kasteleyn states that the number of perfect matchings in a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

can be computed exactly in polynomial time via the

FKT algorithm The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, ...

. The number of perfect matchings in a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

''K_n'' (with ''n'' even) is given by the

double factorial In mathematics, the double factorial or semifactorial of a number , denoted by , is the product of all the integers from 1 up to that have the same parity (odd or even) as . That is, :n!! = \prod_^ (n-2k) = n (n-2) (n-4) \cdots. For even , the ...

(n-1)!!

Perfect matching polytope

{{Main, Matching polytope The perfect matching polytope of a graph is a polytope in R^{, E,} in which each corner is an incidence vector of a perfect matching.

References

Matching (graph theory)

Characterizations

Computation

Perfect matching polytope

See also

References